package Other;

import javax.swing.plaf.IconUIResource;
import java.util.*;

public class leet_15 {
    public static void main(String[] args) {
        Solution_25 p = new Solution_25();
        int[] nums = new int[]{-1,0,1,2,-1,-4};

        List<List<Integer>> result = p.threeSumDoubleLink(nums);
        for(int i=0; i<result.size(); i++){
            System.out.println();
            List<Integer> tmp = result.get(i);
            for (int j = 0; j < tmp.size(); j++) {
                String str = tmp.get(j).toString();
                System.out.print(str);
            }
        }

    }



}


class Solution_25 {
    /**
     * 利用排序与双指针来解决问题
     * 思路：首先排序，在循环数组，
     * 添加2个指针指向当前位置的前后（整体数组的前后）
     * 条件判断：当循环数组的元素指针的元素大于0时，直接返回结果集
     * 当数组循环发生重复时，由于上一个已经讨论完了，直接跳过
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSumDoubleLink(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        // 快排
        quickSort(nums, 0, nums.length-1);

        for(int i=0; i<nums.length; i++){
            if(nums[i]>0){
                // 当最小值大于0时，没必要继续比较不可能为0
                return result;
            }


            if(i==0 || nums[i]!=nums[i-1]){
                // 首位匹配 与 如果上一个与本身相同，就不参与循环
                int left = i+1;
                int right = nums.length-1;
                while(left<right){
                    if(nums[i]+nums[left]+nums[right]==0){
                        // 三数之和为0  添加该数据进入数组
                        List<Integer> tmpList = new ArrayList<>();
                        tmpList.add(nums[i]);
                        tmpList.add(nums[left]);
                        tmpList.add(nums[right]);
                        result.add(tmpList);

                        // 调节2个指针的位置
                        while(left < right && nums[left]==nums[left+1]){
                            // 如果元素相同就跳过
                            left++;
                        }
                        left++;
                        while(left < right && nums[right-1]==nums[right]){
                            // 如果元素相同就跳过
                            right--;
                        }
                        right--;
                    } else if(nums[i]+nums[left]+nums[right]<0){
                        // right已经最大了但还是小于0
                        // 说明left太小了往前走
                        while(left < right && nums[left]==nums[left+1]){
                            // 如果元素相同就跳过
                            left++;
                        }
                        // 上面本身与下一个不相同就跳出循环所以还需要把指针前进
                        left++;

                    } else if(nums[i]+nums[left]+nums[right]>0){
                        // left已经最小了但还是大于0
                        // right太大了 往后退退
                        while(left < right && nums[right-1]==nums[right]){
                            // 如果元素相同就跳过
                            right--;
                        }
                        // 上面前一个与本身不相同就跳出循环所以还需要把指针后退
                        right--;
                    }

                }
            }

        }

        return result;
    }


    /**
     * 快排
     * @param nums   待排序数组
     * @param left   左指针
     * @param right  右指针
     */
    public void quickSort(int[] nums, int left, int right){
        // 结果判断
        if(left>right){return;}
        // 中间值
        int medium = nums[left];

        // 双向指针
        int i=left;
        int j=right;

        while(i!=j){
            // 找到右边小于中间值
            while (i<j && nums[j]>=medium){
                j--;
            }

            // 找到左边大于中间值
            while(i<j && nums[i]<=medium){
                i++;
            }

            if(i<j){
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
            }

        }

        //交换中间指针值与首位置的值
        nums[left] = nums[i];
        nums[i]=medium;
        quickSort(nums, left, i-1);
        quickSort(nums, i+1, right);
    }







    /**
     * 暴力解法 思想 先利用hash将这个数组不相同的2个index的数据之和
     * 全部映射在hash上，在通过求值就可以知道其数据，但最后死于超时~~~
     * 切换解题思路。
     * @param nums 数组
     * @return
     */
    public List<List<Integer>> threeSumViolence(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if(nums.length<1){return result;}


        // 首先使用hash 将数组的2个数组之和加上映射在hash上
        Map<Integer, List<List<Integer>>> hashDouble = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            for(int j=i+1; j<nums.length; j++){
                // 将任意2数之和记做key
                int key = nums[i]+nums[j];
                // 记录这2个数字下标
                List<Integer> numsList = new ArrayList<Integer>();
                numsList.add(i);
                numsList.add(j);
                // 如果已经有这个键值了直接将List加入
                if(hashDouble.containsKey(key)){
                    List<List<Integer>> value = hashDouble.get(key);
                    value.add(numsList);
                    hashDouble.put(key, value);
                }else {
                    // 否则映射到hash表上
                    List<List<Integer>> value = new ArrayList<List<Integer>>();
                    value.add(numsList);
                    hashDouble.put(key, value);
                }
            }
        }
        // 在遍历一次数组 找到符合要求的数组
        for(int i=0; i<nums.length; i++){
            int value = nums[i];
            int key = 0-value;
            if(hashDouble.containsKey(key)){
                // 拿出value 进行比较
                List<List<Integer>> hashValue = hashDouble.get(key);
                for(int j=0; j<hashValue.size(); j++){
                    List<Integer> tmp = findValue(hashValue.get(j), i, nums);
                    if(tmp!=null && !result.contains(tmp)){
                        result.add(tmp);
                    }
                }
            }
        }

        return result;
    }

    /**
     * 暴力解法的一个子方法
     * 寻找这个 数是否合适被放入数组
     * @param value  已经存在的数组下标
     * @param index  待匹配的数组下标
     * @param nums   数组
     * @return       数组下标对应的值的集合
     */
    public List<Integer>  findValue(List<Integer> value, int index, int[] nums){
        if(value.contains(index)){
            return null;
        }

        List<Integer> result = new ArrayList<>();
        int num1 = nums[value.get(0)];
        int num2 = nums[value.get(1)];
        int num3 = nums[index];

        int max = 0;
        int min = 0;

        max = Math.max(num1, num2);
        max = Math.max(max, num3);

        min = Math.min(num1, num2);
        min = Math.min(min, num3);

        result.add(min);
        result.add(num1+num2+num3-max-min);
        result.add(max);
        return result;
    }



}


